Định nghĩa

Định lý nhỏ Fermat khẳng định với mọi số nguyên tố p và mọi số tự nhiên a; ta có:

a p ≡ a ( mod p ) {\displaystyle a^{p}\equiv a{\pmod {p}}} .

Nếu mệnh đề tương tự đúng với số tự nhiên n và với số a nào đó:

a n ≡ a ( mod n ) {\displaystyle a^{n}\equiv a{\pmod {n}}}

thì n được gọi là số nguyên tố xác suất Fermat cơ sở a. Nếu n là hợp số thì nó được gọi là số giả nguyên tố Fermat cơ sở a.

Ví dụ

Số n=561=3.11.17 là một hợp số. Lấy a=2. Ta có 2 560 = 4 280 ≡ 1 ( mod 3 ) {\displaystyle 2^{560}=4^{280}\equiv 1{\pmod {3}}} ; 2 560 = ( 2 10 ) 56 ≡ 1 ( mod 11 ) {\displaystyle 2^{560}={\left(2^{10}\right)}^{56}\equiv 1{\pmod {11}}} và 2 560 = ( 2 16 ) 35 ≡ 1 ( mod 17 ) {\displaystyle 2^{560}={\left(2^{16}\right)}^{35}\equiv 1{\pmod {17}}} . Từ đó 2 560 ≡ 1 ( mod 561 ) {\displaystyle 2^{560}\equiv 1{\pmod {561}}} . Do đó 561 là số giả nguyên tố Fermat cơ sở 2.

Một số kết quả

1. Nếu n là số giả nguyên tố cơ sở 2 thì m = 2 n − 1 {\displaystyle m=2^{n}-1} cũng là số giả nguyên tố cơ sở 2. Từ đó suy ra có vô hạn số giả nguyên tố cơ sở 2.
2. Số Carmichael: Hợp sô n là số Carmichael nếu nó là số giả nguyên tố Fermat với mọi cơ sở a sao cho UCLN(a,n)=1.Ví dụ số 561 ở trên là số Carmichael.